package auxiliary;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

/**
 *
 * @author daq
 */
public class DecisionTree extends Classifier {
    boolean isClassification;
    Node node;
    int depth;
    double throld; 
    static int recursiveTime = 0;
    Map<Double, List<double[]>> splitedList;
    /*
     * Tree node or leaf
     */
    public class Node{
		//attribute numerical:false   attribute discrete:true
		boolean flagCategory;
		//true:smaller; false: not smaller 
		boolean isSmaller;
		//node:0  leaf:1
		int flagNodeLeaf;
		double value;
		double label;
		//classify by the indexth attribute
		int index;
		//children of node
		List<Node> list;
		public Node(){
			flagCategory = false;
			isSmaller = false;
			flagNodeLeaf = 0;
			value = 0;
			label = 0;
			index = 0;
			list = new ArrayList<Node>();
			list.clear();
		}
	}
    public DecisionTree() {
    }
    /*
	* isCategory[k] indicates whether the kth attribut is discrete or continuous, the last attribute is the label
	* features[i] is the feature vector of the ith sample
	* labels[i] is the label of the ith sample
	*/
    @Override
    public void train(boolean[] isCategory, double[][] features, double[] labels) {
        isClassification = isCategory[isCategory.length - 1];
        features = fillMissingValue(isCategory, features);
       	List<double[]> list = new ArrayList<double[]>();
       	for(int i = 0; i < features.length; i++){
       		double [] tempDouble = new double[features[i].length + 1];
       		int j = 0;
       		for(; j < features[i].length; j++){
       			tempDouble[j] = features[i][j];
       		}
       		tempDouble[j] = labels[i];
       		list.add(tempDouble);
       	}
       	if (features[0].length == 9){
       		depth = 2;
       		throld = 0.85;
       	}else if (features[0].length == 19){
       		depth = 8;
       		throld = 0.62;
       	}else if (features[0].length == 21){
       		depth = 1;
       		throld = 1;
       	}else if (features[0].length == 13){
       		depth = 6;
       		throld = 0.78;
       	}else{
       		System.out.println("samples not targeted");
       		System.exit(0);
       	}
        if (isClassification) { // classification
        	node = generateTree(isCategory, list);
        } else {
        	node = generateTree(isCategory, list);
        }
    }
    /*
	* features is the feature vector of the test sample
	* you need to return the label of test sample
	*/
    @Override
    public double predict(double[] features) {
        if (isClassification) { // classification
        	return findLabel(this.node, features);
        	
        } else {
        	return findLabel(this.node, features);
        }
    }
    
    public double findLabel(Node node, double[] features){
    	if (node.flagNodeLeaf == 1){
    		return node.label;
    	}
   		double property = features[node.index];
    	if (node.flagCategory){
    		for(int i = 0; i < node.list.size(); i++){
    			Node childNode = node.list.get(i);
    			if (property == childNode.value){
    				return findLabel(childNode, features);
    			}
    		}
    	}else{
    		for(int i = 0; i < node.list.size(); i++){
    			Node childNode = node.list.get(i);
    			if (property < childNode.value && childNode.isSmaller){
//    				System.out.println("find <");
    				return findLabel(childNode, features);
    			}else if (property >= childNode.value && (!childNode.isSmaller)){
//    				System.out.println("find >=");
    				return findLabel(childNode,features);
    			}
    		}
    	}
    	return Double.NaN;
    }
    public Node generateTree(boolean[] isCategory, List<double[]> list){
    	Node node;
    	double nodeEntropy = 0;
    	if (isClassification){
    		nodeEntropy = getEntropy(list);
    	}else{
    		nodeEntropy = getMSE(list);
    	}
//    	System.out.println("nodeEntropy=" + nodeEntropy);
    	recursiveTime++;
//    	System.out.println("recursiveTime =" + recursiveTime);
    	if(nodeEntropy < throld || recursiveTime > depth){
    		node = createLeaf(list);
    		recursiveTime--;
    		return node;
    	}
    	
    	int splitPosition = splitAttribute(isCategory, list);
    	if (splitPosition == -1){
    		node = createLeaf(list);
    		recursiveTime--;
    		return node;
    	}
    	node = new Node();
    	node.flagNodeLeaf = 0;
    	node.flagCategory = isCategory[splitPosition];
    	node.index = splitPosition;

    	double pivot = Double.MAX_VALUE;
    	Iterator<Entry<Double,List<double[]>>> iter = splitedList.entrySet().iterator();
//    	System.out.println("node.index=" + node.index);
    	if (node.flagCategory == false){
    		while(iter.hasNext()){
    			Map.Entry<Double, List<double[]>> entry = (Map.Entry<Double, List<double[]>>) iter.next();
    			if (pivot > entry.getKey().doubleValue()){
    				pivot = entry.getKey().doubleValue();
    			}
//    			System.out.println("keyValue=" + entry.getKey().doubleValue());
    		}
// 			System.out.println("pivot=" + pivot);
    	}
    	Map<Double, List<double[]>> localSplitedList = splitedList;
    	iter = localSplitedList.entrySet().iterator();
    	while(iter.hasNext()){
    		Map.Entry<Double, List<double[]>> entry = (Map.Entry<Double, List<double[]>>) iter.next();
    		Node childNode = generateTree(isCategory, entry.getValue());
    		if (node.flagCategory){
    			childNode.value = entry.getKey().longValue();
    		}else{
    			childNode.value = pivot;
    			if (pivot < entry.getKey()){
    				childNode.isSmaller = false;
    			}else{
    				childNode.isSmaller = true;
    			}
    		}
    		node.list.add(childNode);
    	}
    	recursiveTime--;
    	return node;
    }
    

    /**
     * 
     * @param isCategory
     * @param list
     * @param splitedList: for numerical attribute, Left List's key is correct pivot
     * @return
     */
    
	public int splitAttribute(boolean[] isCategory, List<double[]> list){
//    	double entropy = Double.POSITIVE_INFINITY;
    	//TODO
		double entropy = 0;
		if (isClassification){
			entropy = getEntropy(list);
		}else{
			entropy = getMSE(list);
		}
    	int splitIndex = -1;
    	for(int i = 1; i < isCategory.length - 2; i++){
    		Map<Double, List<double[]>> tempSplitedList = new HashMap<Double, List<double[]>>();
    		tempSplitedList.clear();
  			double tempEntropy = 0;
    		// attribute is discrete
    		if(isCategory[i]){
    			for(int j = 0; j< list.size(); j++){
    				double[] dLine = list.get(j);
    				Double spliteValue = Double.valueOf(dLine[i]);
//    				System.out.println("spliteValue=" + spliteValue);
    				if (tempSplitedList.containsKey(spliteValue)){
    					List<double[]> tempList = tempSplitedList.get(spliteValue);
    					tempList.add(dLine);
    					tempSplitedList.remove(spliteValue);
    					tempSplitedList.put(spliteValue, tempList);
    				}else{
    					List<double[]> temp = new ArrayList<double[]>();
    					temp.add(dLine);
    					tempSplitedList.put(spliteValue, temp);
    				}
    			}
    			Iterator<Entry<Double, List<double[]>>> ite = tempSplitedList.entrySet().iterator();
    			while(ite.hasNext()){
    				Map.Entry<Double, List<double[]>> entry = (Map.Entry<Double, List<double[]>>)ite.next();
    				List<double[]> eachList = entry.getValue();
    				if (isClassification){
    					tempEntropy += ((double)eachList.size()) / list.size() * getEntropy(eachList);
    				}else{
    					tempEntropy += ((double)eachList.size()) / list.size() * getMSE(eachList);
    				}
    			}
    			if (tempEntropy < entropy && tempEntropy > 0){
    				entropy = tempEntropy;
    				splitIndex = i;
    				splitedList = tempSplitedList;
    			}
    		}else{//attribute is numerical
    			sortByIndexIncrease(i,list);
    			for(int k = 0; k < list.size() - 1; k++){
    				if (list.get(k)[i] == list.get(k+1)[i]){
    					continue;
    				}
    				double pivot = (list.get(k)[i] + list.get(k+1)[i]) / 2;
    				List<double[]> leftList = new ArrayList<double[]>();
    				List<double[]> rightList = new ArrayList<double[]>();
    				for (int j = 0; j <= k; j++){
    					leftList.add(list.get(j));
    				}
    				for (int j = k+1; j < list.size(); j++){
    					rightList.add(list.get(j));
    				}
    				if (isClassification){
    					tempEntropy = ((double)leftList.size()) / list.size() * getEntropy(leftList) 
    						+ ((double)rightList.size()) / list.size() * getEntropy(rightList);
    				}else{
    					tempEntropy = ((double)leftList.size()) / list.size() * getMSE(leftList) 
    						+ ((double)rightList.size()) / list.size() * getMSE(rightList);
    				}
    				if (tempEntropy < entropy && tempEntropy > 0){
    					entropy = tempEntropy;
    					splitIndex = i;
    					splitedList = new HashMap<Double,List<double[]>>();
    					splitedList.put(Double.valueOf(pivot), leftList);
    					splitedList.put(Double.valueOf(pivot+1), rightList);
    				}
    			}
    		}
    	}    	return splitIndex;
    }
    
    public void sortByIndexIncrease(int index, List<double[]> list){
    	double[][] doubleArray = new double[list.size()][list.get(0).length];
    	for (int i = 0; i < list.size(); i++){
    		doubleArray[i] = list.get(i);
    	}
    	for (int i = 0; i < list.size(); i++){
    		for(int j = i+1; j < list.size(); j++){
    			if (doubleArray[i][index] > doubleArray[j][index]){
    				double[] tempForExchange = doubleArray[i];
    				doubleArray[i] = doubleArray[j];
    				doubleArray[j] = tempForExchange;
    			}
    		}
    	}
    	list.clear();
    	for(int i = 0; i < doubleArray.length; i++){
    		list.add(doubleArray[i]);
    	}
    }

    /*
     * create Leaf
     */
    public Node createLeaf(List<double[]> list){
    	Node leaf = new Node();
    	leaf.flagNodeLeaf = 1;
    	if (isClassification){
    		Map<Double,Integer> counter = countLabelsNum(list);
    		int maxNum = 0; 
    		Iterator<Entry<Double, Integer>> iter = counter.entrySet().iterator();
    		while(iter.hasNext()){
    			Map.Entry<Double, Integer> entry = (Map.Entry<Double, Integer>)iter.next();
    			if (entry.getValue().intValue() > maxNum){
    				maxNum = entry.getValue().intValue();
    				leaf.label = entry.getKey().longValue();
    			}
    		}
    	}else{
    		int index = list.get(0).length -1;
    		double average = 0;
    		for(int i = 0; i < list.size(); i++){
    			average += list.get(i)[index];
    		}
    		average = average / list.size();
    		leaf.label = average;
    	}
    	return leaf;
    }
    /*
     * counter each labels num in list
     */
    public Map<Double,Integer> countLabelsNum(List<double[]> list){
    	Map<Double,Integer> counter = new HashMap<Double,Integer>();
    	for(int i = 0; i < list.size(); i++){
    		double[] d = list.get(i);
    		Double labels = Double.valueOf(d[d.length-1]);
    		if(counter.containsKey(labels)){
    			Integer num = counter.get(labels);
    			num++;
    			counter.remove(labels);
    			counter.put(labels, num);
    		}else{
    			counter.put(labels, Integer.valueOf(1));
    		}
    	}
    	return counter;
    }
    /*
     * calculte node's entropy
     */
    public double getEntropy(List<double[]> list){
    	Map<Double,Integer> counter = countLabelsNum(list);
    	double result = 0;
    	Iterator<Entry<Double, Integer>> iter = counter.entrySet().iterator();
		while(iter.hasNext()){
			Map.Entry<Double, Integer> entry = (Map.Entry<Double, Integer>)iter.next();
			double p = entry.getValue().doubleValue() / list.size();
			result -= p * (Math.log(p) / Math.log(2));
		}
    	return result;
    }
    /*
     * calculte node's MSE
     * 
     */
    public double getMSE(List<double[]> list){
    	double average = 0;
    	int index = list.get(0).length - 1;
    	for(int i = 0; i < list.size(); i++){
    		average += list.get(i)[index];
    	}
    	average = average / list.size();
    	double mse = 0;
    	double base = 0;
    	for(int i = 0; i < list.size(); i++){
    		base = average - list.get(i)[index];
    		mse += base * base;
    	}
    	mse = mse / list.size();
    	if (mse == 0){
//    		System.out.println("list.size=" + list.size());
    		double[] d = list.get(0);
    		for (int i = 0; i < d.length; i++){
//    			System.out.print(d[i] + ";");
    		}
    	}
    	return mse;
    }
   /*
    * fill missing values 
    */
    public double[][] fillMissingValue(boolean[] isCategory, double[][] features){
    	Map<Double,Integer> counter = new HashMap<Double,Integer>();
    	List<Integer> missPosition = new ArrayList<Integer>();
    	double sum = 0;
    	for(int i = 0; i < isCategory.length - 1; i++){
    		counter.clear();
    		sum = 0;
    		missPosition.clear();
    		/*
    		 * calculate attributes' sum or times
    		 */
    		for(int j = 0; j < features.length; j++){
    			if (Double.isNaN(features[j][i])){
    				missPosition.add(Integer.valueOf(j));
    				continue;
    			}
    			//attribute is discrete 
    			if (isCategory[i]){
   					if (counter.containsKey(Double.valueOf(features[j][i]))){
   						Integer num = counter.get(Double.valueOf(features[j][i]));
   						num++;
   						counter.remove(features[j][i]);
   						counter.put(Double.valueOf(features[j][i]), num);
   					}else{
   						counter.put(Double.valueOf(features[j][i]), Integer.valueOf(1));
   					}
  				}else{//attribute is numerical
  					sum += features[j][i];
  				}
    		}
    		/*
    		 * fill the missed value
    		 */
   			double filledValue = 0;
    		if(isCategory[i]){
    			int maxNum = -1;
    			Iterator<Entry<Double, Integer>> iter = counter.entrySet().iterator();
    			while(iter.hasNext()){
    				Map.Entry<Double, Integer> entry = (Map.Entry<Double, Integer>)iter.next();
    				Integer value = entry.getValue();
    				if (value.intValue() > maxNum){
    					Double key = entry.getKey();
    					maxNum = value.intValue();
    					filledValue = key.doubleValue();
    				}
    			}
    		}else{
    			int validNum = features.length - missPosition.size();
    			filledValue = sum / validNum;
    		}    		
    		for(int k = 0; k < missPosition.size(); k++){
    				Integer index = missPosition.get(k);
    				features[index.intValue()][i] = filledValue;
    		}
    	}
    	return features;
    }
}
